//
// Created by EDZ on 2022/2/14.
//

#ifndef INC_2022_1_DIVIDE_H
#define INC_2022_1_DIVIDE_H
#include "../head/common.h"
using namespace std;
//112334488
//122
//3377899
//11223
int singleNum(int left,int right,vector<int> nums){
    int mid = (left+right)/2;
    if(left>=right || nums[mid]!=nums[mid-1]&&nums[mid]!=nums[mid+1]){
        return nums[mid];
    }
    if(nums[mid]==nums[mid-1]&&mid%2==0 || nums[mid]==nums[mid+1]&&mid%2==1)
        return singleNum(left,mid-(((mid+1)%2)+1),nums);
    else
        return singleNum(mid+(((mid+1)%2)+1),right,nums);
}
int singleNonDuplicate(vector<int>& nums) {
    int left = 0,right = nums.size()-1;
    return singleNum(left,right,nums);
}

/**
 * https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
 * @param nums
 * @param target
 * @return
 */
int search(vector<int>& nums, int target) {
    int l = 0,r = nums.size()-1;
    while(l<=r){
        int mid = (l+r)/2;
        if(nums[mid]==target)
            return mid;
        else if(nums[l]<=nums[mid]){
            if(nums[l]<=target&&target<=nums[mid])
                r = mid-1;
            else
                l = mid+1;
        }
        else if(nums[mid]<=nums[r]){
            if(nums[mid]<=target&&target<=nums[r])
                l = mid+1;
            else
                r = mid-1;
        }else
            return -1;
    }
    return -1;
}

/**
 * https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 * @param nums
 * @param target
 * @return
 */
int searchBorder(vector<int>& nums,int target,int needEqu){
    int l = 0,r = nums.size()-1,ans = nums.size();
    while(l<=r){
        int mid = (l+r)/2;
        if(needEqu&&nums[mid]>=target || nums[mid]>target){
            r = mid-1;
            ans = mid;
        }else{
            l = mid+1;
        }
    }
    return ans;
}
vector<int> searchRange(vector<int>& nums, int target) {
    int len = nums.size();
    int l = searchBorder(nums,target,true);
    int r = searchBorder(nums,target, false)-1;
    if(l<=r&&l<len&&r<len&&nums[l]==target&&nums[r]==target)
        return {l,r};
    return {-1,-1};
}

/**
 * https://leetcode-cn.com/problems/search-insert-position/
 * @param nums
 * @param target
 * @return
 */
int searchInsert(vector<int>& nums, int target) {
    int l = 0,r = nums.size()-1;
    while(l<=r){
        int mid = (l+r)/2;
        if(nums[mid]>target)
            r = mid-1;
        else if(nums[mid]<target)
            l = mid+1;
        else
            return mid;
    }
    return (l+r)/2;
}

/**
 * https://leetcode-cn.com/problems/sqrtx/
 * @param x
 * @return
 */
int mySqrt(int x) {
    int l = 0,r = x,mid;
    while(l<=r){
        mid = (l+r)/2;
        if(mid*mid>x)
            r = mid - 1;
        else if(mid*mid<x)
            l = mid + 1;
        else
            return mid;
    }
    return (mid*mid)>x?mid-1:mid;
}

/**
 * https://leetcode-cn.com/problems/search-a-2d-matrix/
 * @param matrix
 * @param target
 * @return
 */
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int row = matrix.size();
    if(row==0)
        return false;
    int line = matrix[0].size();
    int l = 0,r = row*line-1,mid;
    while(l<=r){
        mid = (l+r)/2;
        if(matrix[mid/line][mid%line]<target)
            l = mid+1;
        else if(matrix[mid/line][mid%line]>target)
            r = mid-1;
        else
            return true;
    }

    return false;
}

/**
 * https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
 * @param nums
 * @return
 */
int findMin(vector<int>& nums) {
    int l = nums.size();
    if(nums[0]<nums[l-1])
        return nums[0];
    l = 0;
    int r = nums.size()-1;
    while(l<r){
        int mid = (l+r+1)/2;
        if(nums[mid]<nums[r])
            r = mid;
        else{
            l = mid+1;
        }
    }
    return nums[r];
}

int findMin_1(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    return nums[0];
}

/**
 * https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
 * @param numbers
 * @param target
 * @return
 */
vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0,r = numbers.size()-1;
    while(l<r){
        if(numbers[l]+numbers[r]==target){
            return {l,r};
        }else if(numbers[l]+numbers[r]<target){
            l++;
        }else{
            r--;
        }
    }
    return {-1,-1};
}

/**
 * https://leetcode-cn.com/problems/container-with-most-water/
 * @param height
 * @return
 */
int maxArea(vector<int>& height) {
    int n = height.size();
    int maxWater = 0;
    int l = 0,r = n-1;
    while(l<r){
        maxWater = max(maxWater,min(height[l],height[r])*(r-l));
        if(height[l]>height[r])
            r--;
        else
            l++;
    }
    return maxWater;
}
#endif //INC_2022_1_DIVIDE_H
